import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class Solution752 {
    public int openLock(String[] deadends, String target) {
        Queue<String> queue = new LinkedList<>();
        Map<String, Integer> map = new HashMap<>();
        map.put("0000", 0);
        queue.offer("0000");
        for (String deadend : deadends) {
            if (deadend.equals("0000")){
                return -1;
            }
            map.put(deadend, -1);
        }
        while (!queue.isEmpty()) {
            String string = queue.poll();
            for (int i = 0; i < 4; i++) {
                char[] chars = string.toCharArray();
                if (chars[i] == '0') {
                    chars[i] = '1';
                    String s = String.valueOf(chars);
                    if (!map.containsKey(s)) {
                        queue.offer(s);
                        map.put(s, map.get(string) + 1);
                    }
                    chars[i] = '9';
                    s = String.valueOf(chars);
                    if (!map.containsKey(s)) {
                        queue.offer(s);
                        map.put(s, map.get(string) + 1);
                    }
                } else if (chars[i] == '9') {
                    chars[i] = '0';
                    String s = String.valueOf(chars);
                    if (!map.containsKey(s)) {
                        queue.offer(s);
                        map.put(s, map.get(string) + 1);
                    }
                    chars[i] = '8';
                    s = String.valueOf(chars);
                    if (!map.containsKey(s)) {
                        queue.offer(s);
                        map.put(s, map.get(string) + 1);
                    }
                } else {
                    chars[i] = (char) (chars[i] - 1);
                    String s = String.valueOf(chars);
                    if (!map.containsKey(s)) {
                        queue.offer(s);
                        map.put(s, map.get(string) + 1);
                    }
                    chars[i] = (char) (chars[i] + 2);
                    s = String.valueOf(chars);
                    if (!map.containsKey(s)) {
                        queue.offer(s);
                        map.put(s, map.get(string) + 1);
                    }
                }
            }
        }
        return map.getOrDefault(target,-1);
    }

    public static void main(String[] args) {
        System.out.println(new Solution752().openLock(new String[]{"0201","0101","0102","1212","2002"},"0202"));
    }
}
